package _18_剑指OfferII;

import java.util.HashMap;
import java.util.TreeSet;

public class _057_剑指OfferII值和下标之差都在给定的范围内 {


    public static void main(String[] args) {

        _057_剑指OfferII值和下标之差都在给定的范围内 v = new _057_剑指OfferII值和下标之差都在给定的范围内();

        int[] ins = {2147483647,-1,2147483647};
        System.out.println(v.containsNearbyAlmostDuplicate(ins, 1, 2147483647));

    }

    // 桶排序
    // 先不考虑小标索引小于k的情况，如果某两个数的绝对值在此区间的话，我么其实可以假设把这个区间归纳为一个数字
    // 如果这个数字相同，那么就复合条件。
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        HashMap<Long, Long> map = new HashMap<>();
        long size = t + 1;
        for (int i = 0; i < nums.length; ++i) {
            long num = nums[i];
            long bucketId = getBucketId(nums[i], size);
            if (map.containsKey(bucketId)) return true;
            if (map.containsKey(bucketId - 1) && num - map.get(bucketId - 1) <= t) return true;
            if (map.containsKey(bucketId + 1) && map.get(bucketId + 1) - nums[i] <= t) return true;

            map.put(bucketId, num);

            // 滑动窗口元素移出
            if (i >= k) map.remove(getBucketId(nums[i - k], size));
        }
        return false;
    }

    // 确定元素的桶下标位置
    private long getBucketId(int index, long length) {
        return index >= 0? index / length: (index + 1) / length - 1;
    }

    // 滑动窗口 + 有序集合
    public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<>();

        // 对于集合中的元素，满足 x - t <= y <= x + t
        for (int i = 0; i < nums.length; ++i) {
            Long num = set.ceiling(((long)nums[i] - (long)t));
            if (num != null && num <= (long) nums[i] + (long) t) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long)nums[i - k]);
            }
        }
        return false;
    }

}
